{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Car Fleet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #sorting #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #排序 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: carFleet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #车队"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一条单行道上，有 <code>n</code> 辆车开往同一目的地。目的地是几英里以外的&nbsp;<code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>给定两个整数数组&nbsp;<code>position</code>&nbsp;和&nbsp;<code>speed</code>&nbsp;，长度都是 <code>n</code> ，其中&nbsp;<code>position[i]</code>&nbsp;是第 <code>i</code> 辆车的位置，&nbsp;<code>speed[i]</code>&nbsp;是第 <code>i</code> 辆车的速度(单位是英里/小时)。</p>\n",
    "\n",
    "<p>一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车 <strong>以相同的速度</strong> 紧接着行驶。此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。</p>\n",
    "\n",
    "<p><strong>车队</strong><em>&nbsp;</em>是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。</p>\n",
    "\n",
    "<p>即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。</p>\n",
    "\n",
    "<p>返回到达目的地的 <strong>车队数量</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。\n",
    "从 0 处开始的车无法追上其它车，所以它自己就是一个车队。\n",
    "从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。\n",
    "请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> target = 10, position = [3], speed = [3]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong> 只有一辆车，因此只有一个车队。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> target = 100, position = [0,2,4], speed = [4,2,1]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "以0(速度4)和2(速度2)出发的车辆组成车队，在4点相遇。舰队以2的速度前进。\n",
    "然后，车队(速度2)和以4(速度1)出发的汽车组成一个车队，在6点相遇。舰队以1的速度前进，直到到达目标。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == position.length == speed.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt; target &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>0 &lt;= position[i] &lt; target</code></li>\n",
    "\t<li><code>position</code>&nbsp;中每个值都 <strong>不同</strong></li>\n",
    "\t<li><code>0 &lt; speed[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [car-fleet](https://leetcode.cn/problems/car-fleet/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [car-fleet](https://leetcode.cn/problems/car-fleet/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12\\n[10,8,0,5,3]\\n[2,4,1,1,3]', '10\\n[3]\\n[3]', '100\\n[0,2,4]\\n[4,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(speed)\n",
    "        index = sorted(range(n), key = lambda x: position[x])\n",
    "        cnt = 1\n",
    "        prev = (target - position[index[-1]]) / speed[index[-1]]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if (target - position[index[i]]) / speed[index[i]] > prev:\n",
    "                prev = (target - position[index[i]]) / speed[index[i]]\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        args = [i for i in range(n)]\n",
    "        args.sort(key=lambda i: position[i])\n",
    "        st = []\n",
    "        for i in args:\n",
    "            time = (target - position[i]) / speed[i]\n",
    "            while st and st[-1] <= time:\n",
    "                st.pop()\n",
    "            st.append(time)\n",
    "        print(st)\n",
    "        return len(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        \n",
    "        n = len(position)\n",
    "        a = list(range(n))\n",
    "        a.sort(key = lambda x: -position[x])\n",
    "\n",
    "        res = 0\n",
    "        pre = a[0]\n",
    "        last_time = None\n",
    "        for tmp in a[1:]:\n",
    "            if speed[pre] >= speed[tmp]:\n",
    "                res += 1\n",
    "                pre = tmp\n",
    "                last_time = None\n",
    "                continue\n",
    "            far = position[pre] - position[tmp]\n",
    "            speed_diff = speed[tmp] - speed[pre]\n",
    "            if last_time:\n",
    "                pass\n",
    "            else:\n",
    "                last_time = (target-position[pre]) / speed[pre]\n",
    "            if far / speed_diff <= last_time:\n",
    "                continue\n",
    "            else:\n",
    "                res += 1\n",
    "                pre = tmp\n",
    "                last_time = None\n",
    "        \n",
    "        return res+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append( (position[i], speed[i]) )\n",
    "        \n",
    "        res = 0\n",
    "        pre = 0\n",
    "        \n",
    "        for pos, sp in sorted(A, reverse = True):\n",
    "            arrive_time = (target - pos) / sp      # 到达目的地的时间\n",
    "            if pre < arrive_time:     # position 小的 arrive_time 比 position 大的 arrive_time 长\n",
    "                res += 1              # 追不上 position 大的，position 小的自成一体\n",
    "                pre = arrive_time\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        idx = sorted(range(n), key = lambda x: position[x])\n",
    "        stk = []\n",
    "        for i in idx:\n",
    "            p, s = position[i], speed[i]\n",
    "            while stk and s < stk[-1][1] and (target - stk[-1][0]) * (stk[-1][1] - s) >= stk[-1][1] * (p - stk[-1][0]):\n",
    "                stk.pop()\n",
    "\n",
    "            stk.append((p, s))\n",
    "        return len(stk)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append( (position[i], speed[i]) )\n",
    "        \n",
    "        res = 0\n",
    "        pre = 0\n",
    "        \n",
    "        for pos, sp in sorted(A, reverse = True):\n",
    "            arrive_time = (target - pos) / sp      # 到达目的地的时间\n",
    "            if pre < arrive_time:     # position 小的 arrive_time 比 position 大的 arrive_time 长\n",
    "                res += 1              # 追不上 position 大的，position 小的自成一体\n",
    "                pre = arrive_time\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pair = [(p,s) for p,s in zip(position,speed)]\n",
    "        stack = []\n",
    "\n",
    "        #sorted base on position\n",
    "        #add the car that most close to the target first into the stack\n",
    "        for p, s in sorted(pair)[::-1]:\n",
    "            time = (target - p) /s\n",
    "            stack.append(time)\n",
    "            #stack[-2]是离target最近的\n",
    "            #如果离最近的time大于等于第二近的，说明是fleet,删除第二近的（第二近的是stack最表面的time）\n",
    "            if len(stack)>=2 and stack[-1] <= stack[-2]:\n",
    "                stack.pop()\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        stack=[]\n",
    "        for p,s in sorted(zip(position,speed)):\n",
    "            t=(target-p)/s\n",
    "            while stack and stack[-1]<=t:\n",
    "                stack.pop()\n",
    "            stack.append(t)\n",
    "        return len(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pair = [(p,s) for p,s in zip(position, speed)]\n",
    "        stack = []\n",
    "        for p,s in sorted(pair)[::-1]:\n",
    "            \n",
    "            if len(stack)==0 or stack[-1]<(target-p)/s:\n",
    "                stack.append((target-p)/s)\n",
    "               \n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        args = [i for i in range(n)]\n",
    "        args.sort(key=lambda i: position[i])\n",
    "        st = []\n",
    "        for i in args:\n",
    "            time = (target - position[i]) / speed[i]\n",
    "            while st and st[-1] <= time:\n",
    "                st.pop()\n",
    "            st.append(time)\n",
    "        return len(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # arrival = list(zip(position, speed))\n",
    "        # arrival.sort(key=lambda x: (-x[0], -x[1]))\n",
    "        # arrival_time = []\n",
    "        # for each in arrival:\n",
    "        #     tmp_time = (target - each[0]) / each[1]\n",
    "        #     arrival_time.append(tmp_time)\n",
    "        # \n",
    "        # fleet = 1\n",
    "        # standard = arrival_time[0]\n",
    "        # for i in range(1, len(arrival_time)):\n",
    "        #     if arrival_time[i] <= standard:\n",
    "        #         continue\n",
    "        #     fleet += 1\n",
    "        #     standard = arrival_time[i]\n",
    "        # \n",
    "        # return fleet\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i], speed[i]))\n",
    "\n",
    "        res = 0\n",
    "        pre = 0\n",
    "\n",
    "        for pos, sp in sorted(A, reverse=True):\n",
    "            arrive_time = (target - pos) / sp  # 到达目的地的时间\n",
    "            if pre < arrive_time:  # position 小的 arrive_time 比 position 大的 arrive_time 长\n",
    "                res += 1  # 追不上 position 大的，position 小的自成一体\n",
    "                pre = arrive_time\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append( (position[i], speed[i]) )\n",
    "        \n",
    "        res = 0\n",
    "        pre = 0\n",
    "        \n",
    "        for pos, sp in sorted(A, reverse = True):\n",
    "            arrive_time = (target - pos) / sp      # 到达目的地的时间\n",
    "            if pre < arrive_time:     # position 小的 arrive_time 比 position 大的 arrive_time 长\n",
    "                res += 1              # 追不上 position 大的，position 小的自成一体\n",
    "                pre = arrive_time\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: \n",
    "        lst = [(position[i],speed[i]) for i in range(len(position))]\n",
    "        lst.sort(reverse=True)\n",
    "        stact = []\n",
    "        ans = 0\n",
    "        for p,s in lst:\n",
    "            now_time = (target - p) / s\n",
    "            while stact and stact[-1] < now_time:\n",
    "                stact.pop()\n",
    "            if not stact:\n",
    "                ans+=1\n",
    "            stact.append(now_time)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pair = [(p, s) for p, s in zip(position, speed)]\n",
    "        pair.sort(reverse=True)\n",
    "        stack = []\n",
    "        for p, s in pair:  # Reverse Sorted Order\n",
    "            stack.append((target - p) / s)\n",
    "            # print(stack)\n",
    "            if len(stack) >= 2 and stack[-1] <= stack[-2]:\n",
    "                stack.pop()\n",
    "            # print(stack)\n",
    "        return len(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pair = [(p, s) for p, s in zip(position, speed)]\n",
    "        pair.sort(reverse=True)\n",
    "        stack = []\n",
    "        for (p, s) in pair:\n",
    "            tmp = (target - p) / s\n",
    "            stack.append(tmp)\n",
    "            if len(stack) >= 2 and stack[-1] <= stack[-2]:\n",
    "                # pop the faster car\n",
    "                stack.pop()\n",
    "        \n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        index = [i for i in range(n)]\n",
    "        index.sort(key = lambda x: position[x],reverse = True)\n",
    "        st = []\n",
    "        time = [0] * n\n",
    "        for i in range(n):\n",
    "            time[i] = (target - position[index[i]]) /speed[index[i]]\n",
    "        for i in range(n):\n",
    "            m = time[i]\n",
    "            if st and st[-1] >= time[i]:\n",
    "                m = st[-1]\n",
    "                st.pop()\n",
    "            st.append(m)\n",
    "        return len(st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i], speed[i]))\n",
    "        \n",
    "        res = 0\n",
    "        pre = 0\n",
    "        \n",
    "        for pos, sp in sorted(A, reverse = True):\n",
    "            arrive_time = (target - pos) / sp      # 到达目的地的时间\n",
    "            if pre < arrive_time:     # position 小的 arrive_time 比 position 大的 arrive_time 长\n",
    "                res += 1              # 追不上 position 大的，position 小的自成一体\n",
    "                pre = arrive_time\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        a = []\n",
    "        for i in range(len(position)):\n",
    "            a.append((position[i],speed[i]))\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for i,j in sorted(a,reverse = True):\n",
    "            time = (target - i) / j\n",
    "            if time > pre:\n",
    "                res += 1\n",
    "                pre = time\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A=[]\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i],speed[i]))\n",
    "        res=0\n",
    "        pre=0\n",
    "        for pos,sp in sorted(A,reverse=True):\n",
    "            arrive_time=(target-pos)/sp\n",
    "            if pre<arrive_time:\n",
    "                res+=1\n",
    "                pre=arrive_time\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A=[]\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i],speed[i]))\n",
    "        res=0\n",
    "        pre=0\n",
    "        for pos,sp in sorted(A,reverse=True):\n",
    "            arrive_time=(target-pos)/sp\n",
    "            if pre<arrive_time:\n",
    "                res+=1\n",
    "                pre=arrive_time\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        idx = sorted(range(n),key = lambda i:-position[i])\n",
    "        ans,pre = 0,-1\n",
    "        for i in idx:\n",
    "            t = (target-position[i])/speed[i]\n",
    "            if t > pre:\n",
    "                ans += 1\n",
    "                pre = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        # 计算所有车到达的时间，按照距离排序后，使用单调递增栈，只用记录前缀最大值即可\n",
    "        rank = sorted(range(n), key=lambda i:target - position[i])\n",
    "        \n",
    "        ans = 0\n",
    "        mx_time = 0\n",
    "        for i in rank:\n",
    "            time = (target - position[i]) / speed[i]\n",
    "            if time > mx_time:\n",
    "                mx_time = time\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pairs = list(zip(position, speed))\n",
    "        pairs.sort(reverse=True)\n",
    "        maxTime = 0\n",
    "        res = 0\n",
    "        for p, s in pairs:\n",
    "            cur = (target - p) / s\n",
    "            if cur <= maxTime:\n",
    "                continue \n",
    "            maxTime = cur \n",
    "            res += 1 \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        tmp = []\n",
    "        for i in range(len(position)):\n",
    "            tmp.append((position[i], speed[i]))\n",
    "        # 从大到小排\n",
    "        tmp.sort(reverse=True)\n",
    "        # print(tmp)\n",
    "\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        for pos, sp in tmp:\n",
    "            arrive_time = (target - pos) / sp\n",
    "            if pre < arrive_time:\n",
    "                res += 1\n",
    "                pre = arrive_time\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pos_speed = [[p, s] for p, s in zip(position, speed)]\n",
    "        pos_speed.sort(reverse = True)\n",
    "        stack = []\n",
    "        for p, s in pos_speed:\n",
    "            stack.append((target - p) / s)\n",
    "            if len(stack) >= 2 and stack[-1] <= stack[-2]:\n",
    "                stack.pop()\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pos_sp = []\n",
    "        n = len(position)\n",
    "        for i in range(n):\n",
    "            pos_sp.append((position[i], speed[i]))\n",
    "        pos_sp.sort(reverse=True)\n",
    "        res = 1\n",
    "        lasttime = (target-pos_sp[0][0])/float(pos_sp[0][1])\n",
    "        for i in range(1, n):\n",
    "            thistime = (target-pos_sp[i][0])/float(pos_sp[i][1])\n",
    "            if thistime <= lasttime:\n",
    "                continue\n",
    "            else:\n",
    "                lasttime = thistime\n",
    "                res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        def time(p, s):\n",
    "            return (target - p) / s\n",
    "        cars = [[p, s] for p, s in zip(position, speed)]\n",
    "        cars.sort()\n",
    "        n = len(cars)\n",
    "        res = []\n",
    "        for i in reversed(range(n)):\n",
    "            p, s = cars.pop()\n",
    "            if not res:\n",
    "                res.append([p, s])\n",
    "            elif time(p, s) > time(res[-1][0], res[-1][1]):\n",
    "                res.append([p, s])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import ceil\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "      cars = sorted(list(zip(position, speed)))\n",
    "      stack = []\n",
    "      for pos, s in cars:\n",
    "        step = (target-pos)/s\n",
    "        while stack and step>=stack[-1]:\n",
    "          stack.pop()\n",
    "        stack.append(step)\n",
    "\n",
    "      return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        A = []\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i], speed[i]))\n",
    "        # 对 ((position[i], speed[i])) 进行排序，position 大的排前面\n",
    "        sorted_A = sorted(A, reverse =True)\n",
    "\n",
    "        res = 0\n",
    "        pre = 0\n",
    "\n",
    "        for pos, sp in sorted_A:\n",
    "            arrive_time = (target - pos)/ sp\n",
    "            if pre < arrive_time:\n",
    "                res += 1\n",
    "                pre = arrive_time\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        # 计算所有车到达的时间，按照距离排序后，使用单调递增栈，只用记录前缀最大值即可\n",
    "        position = [target - p for p in position]\n",
    "        rank = sorted(range(n), key=lambda i:position[i])\n",
    "        \n",
    "        ans = 0\n",
    "        mx_time = 0\n",
    "        for i in rank:\n",
    "            time = position[i] / speed[i]\n",
    "            if time > mx_time:\n",
    "                mx_time = time\n",
    "                ans += 1\n",
    "        return ans\n",
    "                \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        ps = sorted(zip(position, speed), key=lambda x: x[0], reverse=True)\n",
    "        ans = 0\n",
    "        cur_finish_time = -inf\n",
    "        for p, s in ps:\n",
    "            if (target - p) / s > cur_finish_time:\n",
    "                cur_finish_time = (target - p) / s\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        :type target: int\n",
    "        :type position: List[int]\n",
    "        :type speed: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(speed)\n",
    "        length = 0\n",
    "        stack = []\n",
    "        time = [(target-position[i])/speed[i] for i in range(n)]\n",
    "        # print(\"time:\",time)\n",
    "        order = [-1 for i in range(target)]\n",
    "        \n",
    "        if len(position)==1:\n",
    "            return 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            order[position[i]]=time[i]\n",
    "        \n",
    "        last = target*100\n",
    "        ans = 1\n",
    "        # print(order)\n",
    "        first = False\n",
    "        \n",
    "        for i in range(target-1,-1,-1):\n",
    "            \n",
    "            if order[i]==-1:\n",
    "                continue\n",
    "            if first==False:\n",
    "                stack.insert(0,i)\n",
    "                first = True\n",
    "                continue\n",
    "                \n",
    "           # while order[stack[0]]>order[i]:                \n",
    "           #     ans+=1\n",
    "           #     stack.pop(0)\n",
    "           #     if len(stack)==0:\n",
    "           #         break\n",
    "           # stack.insert(0, i)\n",
    "            if order[i]>order[stack[0]]:\n",
    "                ans+=1\n",
    "                stack[0]=i\n",
    "        \n",
    "            \n",
    "        # print(ans)\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # 排序\n",
    "        cars = sorted(zip(position,speed),key=lambda x:x[0],reverse=True)\n",
    "        max_time = 0\n",
    "        ans = len(cars)\n",
    "        for p,s in cars:\n",
    "            time = (target-p)/s\n",
    "            # print(p,s,time)\n",
    "            if time<=max_time: # 追上组成车队\n",
    "                ans -=1\n",
    "            else:\n",
    "                max_time = time \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars = sorted(zip(position, speed), key=lambda x: x[0], reverse=True)\n",
    "        fleets = 0\n",
    "        stack = []\n",
    "\n",
    "        for pos, spd in cars:\n",
    "            time_to_arrive = (target - pos) / spd\n",
    "\n",
    "            if not stack:\n",
    "                stack.append(time_to_arrive)\n",
    "                fleets += 1\n",
    "            else:\n",
    "                if time_to_arrive > stack[-1]:\n",
    "                    stack.append(time_to_arrive)\n",
    "                    fleets += 1\n",
    "\n",
    "        return fleets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pair=[[p,s]for p,s in zip(position,speed)]\n",
    "        stack=[]\n",
    "        for p,s in sorted(pair)[::-1]:\n",
    "            stack.append((target-p)/s)\n",
    "            if len(stack)>=2 and stack[-1]<=stack[-2]:\n",
    "                stack.pop()\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        stack=[]\n",
    "        n=len(position)\n",
    "        cards=sorted(zip(position,speed))\n",
    "        ans=0\n",
    "        p=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            p.append((target-cards[i][0])/cards[i][1])\n",
    "        x=p[0]\n",
    "        for i in range(1,n):\n",
    "            if x>=p[i]:\n",
    "                continue\n",
    "            else:\n",
    "                x=p[i]\n",
    "                ans+=1\n",
    "        ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "\n",
    "        pairs = [(position[i],speed[i]) for i in range(len(position))]\n",
    "        pairs = sorted(pairs, key = lambda x: x[0])[::-1]  #ones near target first\n",
    "\n",
    "        fleet = 0\n",
    "        while pairs:\n",
    "            newPairs = []\n",
    "           \n",
    "            for a,b in pairs:\n",
    "                #print(newPairs)\n",
    "            \n",
    "                curA = a+b\n",
    "\n",
    "                if newPairs and newPairs[-1][0] <= curA:\n",
    "                    prevA, prevB = newPairs[-1]\n",
    "                    if prevA<target:\n",
    "                        newPairs[-1] = (prevA,min(b,prevB))\n",
    "                    else:\n",
    "                        time = (prevA- target)/prevB\n",
    "                        if curA-b*time>=target:\n",
    "                            newPairs[-1] = (prevA,min(b,prevB))\n",
    "                        else:\n",
    "                            newPairs.append((curA,b))\n",
    "\n",
    "                else:\n",
    "                    newPairs.append((curA,b))\n",
    "            \n",
    "            for a,b in newPairs:\n",
    "                if a>=target:\n",
    "                    fleet+=1\n",
    "            pairs = [(a,b) for a,b in newPairs if a<target]\n",
    "                \n",
    "        return fleet\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        time = [0]*n\n",
    "        for i in range(n):\n",
    "            time[i] = (target-position[i])/speed[i]\n",
    "        s = sorted(zip(position,time),reverse=True)\n",
    "        t = 0\n",
    "        count = 0\n",
    "        for _,j in s:\n",
    "            if j > t:\n",
    "                count += 1\n",
    "                t = j\n",
    "        return count\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        stack = []\n",
    "        cars = zip(position, speed)\n",
    "        cars = sorted(cars, reverse = True)\n",
    "        times = [0]*n\n",
    "        for i in range(n):\n",
    "            times[i] = (target-cars[i][0])/cars[i][1]\n",
    "        for i in range(n):\n",
    "            m = times[i]\n",
    "            if stack and stack[-1] >= times[i]:\n",
    "                m = stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(m)\n",
    "        return len(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        time = [(target - p) / s for p, s in sorted(list(zip(position, speed)), reverse=True)]\n",
    "        prev, ans = time[0], 1\n",
    "        for i in range(1, len(time)):\n",
    "            if time[i] > prev:\n",
    "                ans += 1\n",
    "                prev = time[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars = [(p, s) for p, s in zip(position, speed)]\n",
    "        cars = sorted(cars, key=lambda x: x[0])\n",
    "\n",
    "        # print(cars)\n",
    "\n",
    "        n = len(speed)\n",
    "        res = n\n",
    "        times = [0.0] * n\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # print(stack)\n",
    "            while stack:\n",
    "                j = stack[-1]\n",
    "                if cars[i][1] > cars[j][1]:\n",
    "                    t = (cars[j][0] - cars[i][0]) / (cars[i][1] - cars[j][1])\n",
    "                    if t <= times[j]:\n",
    "                        times[i] = times[j]\n",
    "                        res -= 1\n",
    "                        break\n",
    "                stack.pop()\n",
    "\n",
    "            if not stack:\n",
    "                t = (target - cars[i][0]) / cars[i][1]\n",
    "                times[i] = t\n",
    "            stack.append(i)\n",
    "        # print(times)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        a = [0]*n\n",
    "        for i in range(n):\n",
    "            a[i]=[position[i],speed[i]]\n",
    "        a.sort(key=lambda x:x[0])\n",
    "        for i in range(n):\n",
    "            a[i][1] = (target - a[i][0])/a[i][1]\n",
    "        before = 0\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if a[i][1] > before:\n",
    "                before = a[i][1]\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars=sorted(zip(position,speed))\n",
    "        times=[float(target-p)/s for p,s in cars]\n",
    "        res=0\n",
    "        while len(times)>1:\n",
    "            lead=times.pop()\n",
    "            if lead<times[-1]:\n",
    "                res+=1  #未能超过，车队加一\n",
    "            else:\n",
    "                times[-1]=lead\n",
    "        return res+bool(times)\n",
    "        \n",
    "\n",
    "        A=[]\n",
    "        for i in range(len(position)):\n",
    "            A.append((position[i],speed[i]))\n",
    "        res=0\n",
    "        pre=0\n",
    "        for pos,sp in sorted(A,reverse=True):\n",
    "            arrive_time=(target-pos)/sp\n",
    "            if pre<arrive_time:\n",
    "                res+=1\n",
    "                pre=arrive_time\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        cars = []\n",
    "        for i in range(n):\n",
    "            cars.append((position[i], speed[i]))\n",
    "        cars.sort(key=lambda car:car[0])\n",
    "\n",
    "        time = []\n",
    "        for car in cars:\n",
    "            time.append((target-car[0])/car[1])\n",
    "        \n",
    "        stack = []\n",
    "        for t in time:\n",
    "            while stack and t >= stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(t)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        arr = list(zip(position, speed))\n",
    "        arr.sort(key=lambda x: -x[0])\n",
    "        stack = []\n",
    "        \n",
    "        def get_arrival_time(pos, sp):\n",
    "            return (target - pos) / sp\n",
    "\n",
    "\n",
    "        for pos, sp in arr:\n",
    "            if stack and get_arrival_time(pos, sp) <= get_arrival_time(stack[-1][0], stack[-1][1]):\n",
    "                continue\n",
    "\n",
    "            stack.append([pos, sp])\n",
    "        \n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\r\n",
    "        cars=list(zip(position, speed))\r\n",
    "        cars.sort(key=lambda x:-x[0])\r\n",
    "        res=0\r\n",
    "        t=-1\r\n",
    "        for p,s in cars:\r\n",
    "            tmp=(target-p)/s\r\n",
    "            if tmp>t:\r\n",
    "                t=tmp\r\n",
    "                res+=1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars = sorted(zip(position, speed))\n",
    "        times = [(target-pos)/sp for pos, sp in cars]\n",
    "\n",
    "        res = 0\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            if lead < times[-1]: res += 1\n",
    "            else: times[-1] = lead\n",
    "\n",
    "        return res + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def carFleet(self, target, position, speed):\n",
    "        cars = sorted(zip(position, speed))\n",
    "        times = [float(target - p) / s for p, s in cars]\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            if lead < times[-1]: ans += 1  # if lead arrives sooner, it can't be caught\n",
    "            else: times[-1] = lead # else, fleet arrives at later time 'lead'\n",
    "        return ans + bool(times) # remaining car is fleet (if it exists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars = sorted(zip(position, speed))\n",
    "        # print(cars)\n",
    "        times = [float(target - p) / s for p, s in cars]\n",
    "        # print(times)\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            # print('pop', lead)\n",
    "            # print('times', times)\n",
    "            if lead < times[-1]: \n",
    "                ans += 1  # if lead arrives sooner, it can't be caught\n",
    "                # print('update ans=', ans)\n",
    "            else: times[-1] = lead # else, fleet arrives at later time 'lead'\n",
    "        #     print('times', times)\n",
    "        # print('ans', ans)\n",
    "        # print('bool(times)',bool(times))\n",
    "        print(times)\n",
    "        return ans + bool(times) # remaining car is fleet (if it exists)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        times = [(target - pos) / spd for pos, spd in sorted(zip(position, speed))]\n",
    "\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            lead_time = times.pop()\n",
    "            if lead_time < times[-1]:\n",
    "                ans += 1\n",
    "            else:\n",
    "                times[-1] = lead_time\n",
    "        \n",
    "        return ans + bool(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        if not position:\n",
    "            return 0\n",
    "        \n",
    "        dictmp = dict(zip(position, speed))\n",
    "        dictposition = sorted(dictmp.keys(),reverse=True)\n",
    "        carnums = 1\n",
    "        for i in range(len(position) - 1):\n",
    "            if (target - dictposition[i]) / dictmp[dictposition[i]] \\\n",
    "                < (target - dictposition[i + 1]) / dictmp[dictposition[i + 1]]:\n",
    "                carnums += 1\n",
    "            else:\n",
    "                dictposition[i + 1] = dictposition[i]\n",
    "        return carnums\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def carFleet(self, target, position, speed):\n",
    "        cars = sorted(zip(position, speed))\n",
    "        times = [float(target - p) / s for p, s in cars]\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            if lead < times[-1]: ans += 1  # if lead arrives sooner, it can't be caught\n",
    "            else: times[-1] = lead # else, fleet arrives at later time 'lead'\n",
    "\n",
    "        return ans + bool(times) # remaining car is fleet (if it exists)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        arr = sorted(zip(position, speed))\n",
    "        times = [(target - p) / s for p, s in arr]\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            t = times.pop()\n",
    "            if times[-1] <= t:\n",
    "                times[-1] = t\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans + bool(times)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "\n",
    "        pairs = [(position[i],speed[i]) for i in range(len(position))]\n",
    "        pairs = sorted(pairs, key = lambda x: x[0])[::-1]  #ones near target first\n",
    "\n",
    "        fleet = 0\n",
    "        while pairs:\n",
    "            newPairs = []\n",
    "            print(pairs)\n",
    "            print(\"--------\")\n",
    "            \n",
    "            for a,b in pairs:\n",
    "                #print(newPairs)\n",
    "            \n",
    "                curA = a+b\n",
    "\n",
    "                if newPairs and newPairs[-1][0] <= curA:\n",
    "                    prevA, prevB = newPairs[-1]\n",
    "                    if prevA<target:\n",
    "                        newPairs[-1] = (prevA,min(b,prevB))\n",
    "                    else:\n",
    "                        time = (prevA- target)/prevB\n",
    "                        if curA-b*time>=target:\n",
    "                            newPairs[-1] = (prevA,min(b,prevB))\n",
    "                        else:\n",
    "                            newPairs.append((curA,b))\n",
    "\n",
    "                else:\n",
    "                    newPairs.append((curA,b))\n",
    "            \n",
    "            for a,b in newPairs:\n",
    "                if a>=target:\n",
    "                    fleet+=1\n",
    "            pairs = [(a,b) for a,b in newPairs if a<target]\n",
    "                \n",
    "        return fleet\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        tab = {}\n",
    "        for i in range(n):\n",
    "            tab[position[i]]=speed[i]\n",
    "        position.sort()\n",
    "        ans=0\n",
    "        i=n-1\n",
    "        print(position)\n",
    "        while i>=0:\n",
    "            if i==0 or tab[position[i-1]]<=tab[position[i]]:\n",
    "                ans+=1 #无法相遇\n",
    "                i-=1\n",
    "                continue\n",
    "            time = (target-position[i])/tab[position[i]]\n",
    "            j=i-1\n",
    "            while j>=0 and tab[position[j]]>tab[position[i]]:\n",
    "                time_j = (target-position[j])/tab[position[j]]\n",
    "                # print(i,j,time,time_j)\n",
    "                if time_j>time:\n",
    "                    break\n",
    "                else:\n",
    "                    j-=1\n",
    "            ans+=1\n",
    "            i=j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        nodes = []\n",
    "        n = len(speed)\n",
    "\n",
    "        for i in range(n):\n",
    "            nodes.append([position[i], speed[i]])\n",
    "        nodes.sort(key = lambda x : (-x[0]))\n",
    "        # print(nodes)\n",
    "\n",
    "        stack = []\n",
    "        for pos, spe in nodes:\n",
    "            if stack and stack[-1] >= (target - pos) / spe:\n",
    "                continue\n",
    "            stack.append((target - pos) / spe)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        carlist = {position[i]:speed[i] for i in range(len(position))}\n",
    "        possort = sorted(carlist.keys())\n",
    "        spesort = [carlist[pos] for pos in possort]\n",
    "\n",
    "        lasttime = [(target - possort[i]) / spesort[i] for i in range(len(position))]\n",
    "\n",
    "        result = 0\n",
    "        stack = []\n",
    "        for i in range(len(lasttime)):\n",
    "            while stack != [] and lasttime[i] >= stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(lasttime[i])\n",
    "        \n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        times={}\n",
    "        for idx,i in enumerate(position):\n",
    "            times.setdefault(i,(target-position[idx])/speed[idx])\n",
    "        stack = []\n",
    "        for i in sorted(times):\n",
    "            while stack and stack[-1] <= times[i]:\n",
    "                stack.pop()\n",
    "            stack.append(times[i])\n",
    "        return len(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        ts = dict()\n",
    "        for p, s in zip(position, speed):\n",
    "            ts[p] = (target - p) / s\n",
    "        position.sort()\n",
    "        ans = 0\n",
    "        q = deque()\n",
    "        for i in range(len(position) - 1, -1, -1):\n",
    "            while q and q[-1] < ts[position[i]]:\n",
    "                q.pop()\n",
    "            if not q:\n",
    "                ans += 1\n",
    "            q.append(ts[position[i]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        times = {}\n",
    "        for index, i in enumerate(position):\n",
    "            times.setdefault(i, (target - i) / speed[index])\n",
    "\n",
    "        stack = []\n",
    "        for key in sorted(times):\n",
    "            while stack and stack[-1] <= times[key]:\n",
    "                stack.pop()\n",
    "            stack.append(times[key])\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        stack = []\n",
    "        tmp = []\n",
    "        cars = zip(position, speed)\n",
    "        cars = sorted(cars, reverse=True)\n",
    "        print(cars)\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            usetime = (target - cars[i][0]) / cars[i][1]\n",
    "            stack.append(usetime)\n",
    "        tmp.append(stack[0])\n",
    "        for i in range(n - 1):\n",
    "            if stack[i] < stack[i + 1]:\n",
    "                tmp.append(stack[i + 1])\n",
    "            else:\n",
    "                stack[i + 1] = stack[i]\n",
    "        return len(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        d = [(target - p,s) for p,s in zip(position,speed)]\n",
    "        d.sort()\n",
    "        stack = []\n",
    "        print(d)\n",
    "        for i, (x,s) in enumerate(d):\n",
    "            if stack and stack[-1] >= x / s:\n",
    "                continue\n",
    "            stack.append(x /s)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        time_map = {}\n",
    "        n = len(position)\n",
    "        for i in range(n):\n",
    "            time = (target - position[i]) / speed[i]\n",
    "            time_map[position[i]] = time\n",
    "        position.sort()\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            time = time_map[position[i]]\n",
    "            while stack and time >= stack[-1]:\n",
    "                stack.pop()\n",
    "            stack.append(time)\n",
    "        return len(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        time_arrvial = [[position[i],(target-position[i])/speed[i]] for i in range(n)]\n",
    "        time_arrvial.sort(key=lambda x:x[0])\n",
    "        # print(time_arrvial)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and stack[-1] <= time_arrvial[i][1]:\n",
    "                stack.pop()\n",
    "            stack.append(time_arrvial[i][1])\n",
    "        return len(stack)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def carFleet(self, target, position, speed):\n",
    "        cars = sorted(zip(position, speed))\n",
    "        print(cars)\n",
    "        times = [float(target - p) / s for p, s in cars]\n",
    "        ans = 0\n",
    "        print(times)\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            if lead < times[-1]: ans += 1  # if lead arrives sooner, it can't be caught\n",
    "            else: times[-1] = lead # else, fleet arrives at later time 'lead'\n",
    "\n",
    "        return ans + bool(times) # remaining car is fleet (if it exists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # cars = [[position[i], speed[i]] for i in range(len(position))]\n",
    "        # cars = sorted(cars, key=lambda x: x[0], reverse=True)\n",
    "        # res = 0\n",
    "        # pre_time = 0\n",
    "        # for pos, speed in cars:\n",
    "        #     time = (target - pos) / speed\n",
    "        #     if pre_time < time:\n",
    "        #         res += 1\n",
    "        #         pre_time = time\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # sort_idx = list(range(len(position)))\n",
    "        # sort_idx = sorted(sort_idx, key=lambda i: -1 * position[i])\n",
    "        # #sort_idx = np.arange(len(positon)).sort(key=lambda i :position[i])\n",
    "        # position_new = [position[i] for i in sort_idx]\n",
    "        # speed_new = [speed[i] for i in sort_idx]\n",
    "\n",
    "        # print(position_new)\n",
    "        # print(speed_new)\n",
    "\n",
    "        # car_set_num = 1\n",
    "        # last_car = 0\n",
    "        # last_car_time =(target - position_new[last_car]) / speed_new[last_car]\n",
    "        # for i in range(1, len(position)):\n",
    "        #     new_car_time = (target - position_new[i]) / speed_new[i]\n",
    "        #     if new_car_time > last_car_time:\n",
    "        #         last_car_time = new_car_time\n",
    "        #         car_set_num += 1\n",
    "        \n",
    "        # return car_set_num \n",
    "\n",
    "\n",
    "\n",
    "        distance = [target - p for p in position]\n",
    "        ptime = [(position[i], distance[i]/speed[i]) for i in range(len(speed))]\n",
    "        ptime = sorted(ptime, reverse=True)\n",
    "        ts = ptime[0][1]\n",
    "        groups_count = 1\n",
    "        # print(ptime)\n",
    "        for t in ptime[1:]:\n",
    "            if t[1] > ts:\n",
    "                groups_count += 1\n",
    "                ts = t[1]\n",
    "        return groups_count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # cur_speed = {}\n",
    "        # for i in range(len(position)):\n",
    "        #     cur_speed[position[i]] = speed[i]\n",
    "        # num = 0\n",
    "        # while cur_speed:\n",
    "        #     next_speed = {}\n",
    "        #     reach = []\n",
    "        #     for pos,val in cur_speed.items():\n",
    "        #         if pos >= target and not pos in reach:\n",
    "        #             reach.append(pos)\n",
    "        #             continue\n",
    "        #         next_pos = pos+val\n",
    "        #         if not next_pos in next_speed:\n",
    "        #             next_speed[next_pos] = val\n",
    "        #         else:\n",
    "        #             next_speed[next_pos] = min(val, next_speed[next_pos])\n",
    "            \n",
    "        #     num += len(reach)\n",
    "        #     cur_speed = next_speed\n",
    "        # return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # cars = [[position[i], speed[i]] for i in range(len(position))]\n",
    "        # cars = sorted(cars, key=lambda x: x[0], reverse=True)\n",
    "        # res = 0\n",
    "        # pre_time = 0\n",
    "        # for pos, speed in cars:\n",
    "        #     time = (target - pos) / speed\n",
    "        #     if pre_time < time:\n",
    "        #         res += 1\n",
    "        #         pre_time = time\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # sort_idx = list(range(len(position)))\n",
    "        # sort_idx = sorted(sort_idx, key=lambda i: -1 * position[i])\n",
    "        # #sort_idx = np.arange(len(positon)).sort(key=lambda i :position[i])\n",
    "        # position_new = [position[i] for i in sort_idx]\n",
    "        # speed_new = [speed[i] for i in sort_idx]\n",
    "\n",
    "        # print(position_new)\n",
    "        # print(speed_new)\n",
    "\n",
    "        # car_set_num = 1\n",
    "        # last_car = 0\n",
    "        # last_car_time =(target - position_new[last_car]) / speed_new[last_car]\n",
    "        # for i in range(1, len(position)):\n",
    "        #     new_car_time = (target - position_new[i]) / speed_new[i]\n",
    "        #     if new_car_time > last_car_time:\n",
    "        #         last_car_time = new_car_time\n",
    "        #         car_set_num += 1\n",
    "        \n",
    "        # return car_set_num \n",
    "\n",
    "\n",
    "\n",
    "        distance = [target - p for p in position]\n",
    "        ptime = [(position[i], distance[i]/speed[i]) for i in range(len(speed))]\n",
    "        ptime = sorted(ptime, reverse=True)\n",
    "        ts = ptime[0][1]\n",
    "        groups_count = 1\n",
    "        # print(ptime)\n",
    "        for t in ptime[1:]:\n",
    "            if t[1] > ts:\n",
    "                groups_count += 1\n",
    "                ts = t[1]\n",
    "        return groups_count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # cur_speed = {}\n",
    "        # for i in range(len(position)):\n",
    "        #     cur_speed[position[i]] = speed[i]\n",
    "        # num = 0\n",
    "        # while cur_speed:\n",
    "        #     next_speed = {}\n",
    "        #     reach = []\n",
    "        #     for pos,val in cur_speed.items():\n",
    "        #         if pos >= target and not pos in reach:\n",
    "        #             reach.append(pos)\n",
    "        #             continue\n",
    "        #         next_pos = pos+val\n",
    "        #         if not next_pos in next_speed:\n",
    "        #             next_speed[next_pos] = val\n",
    "        #         else:\n",
    "        #             next_speed[next_pos] = min(val, next_speed[next_pos])\n",
    "            \n",
    "        #     num += len(reach)\n",
    "        #     cur_speed = next_speed\n",
    "        # return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        distance = [target - p for p in position]\n",
    "        time = [d / s for d, s in zip(distance, speed)]\n",
    "        distance_time = list(zip(distance, time))\n",
    "        distance_time.sort()\n",
    "\n",
    "        count = 1\n",
    "        stack = []\n",
    "        for d, t in distance_time:\n",
    "            if not stack:\n",
    "                stack.append(t)\n",
    "                continue\n",
    "            if t > stack[-1]:\n",
    "                count += 1\n",
    "                stack.append(t)\n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        # combine the position and speed, then sort\n",
    "        def takefirst(ele):\n",
    "            return ele[0]\n",
    "        init = []\n",
    "        for idx in range(len(position)):\n",
    "            init.append([position[idx], speed[idx]])\n",
    "        init.sort(key = takefirst, reverse = True)\n",
    "\n",
    "        for idx, element in enumerate(init):\n",
    "            init[idx] = [element[0], element[1], (target - element[0]) / element[1]]\n",
    "        \n",
    "        res = [init[0][2]]\n",
    "        for idx in range(1, len(init)):\n",
    "            if init[idx][2] < init[idx - 1][2]:\n",
    "                init[idx][2] = init[idx - 1][2]\n",
    "            res.append(init[idx][2])\n",
    "        return len(set(res))\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        car_speed_dic = {}\n",
    "        for i,v in enumerate(position):\n",
    "            car_speed_dic[v] = speed[i]\n",
    "        position.sort(reverse=True)\n",
    "        \n",
    "        data = [position[0]]\n",
    "        car_time = {position[0]: (target - data[-1]) / car_speed_dic[data[-1]]}\n",
    "        p_len = len(position)\n",
    "        for i in range(1, p_len):\n",
    "            v  = position[i]\n",
    "            t_time =  (target - v) / car_speed_dic[v]\n",
    "            if t_time <= car_time[data[-1]]:\n",
    "                car_time[v] = car_time[data[-1]]\n",
    "                data[-1] = v\n",
    "                continue\n",
    "            data.append(position[i])\n",
    "            car_time[v] = t_time\n",
    "            \n",
    "        return len(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        \n",
    "        carlist = list(zip(position,speed))\n",
    "        car_lined = set()\n",
    "        carlines = {}\n",
    "        \n",
    "        carlen = len(position)\n",
    "        carlistnum = 0\n",
    "\n",
    "        if carlen <= 1:\n",
    "            return carlen\n",
    "\n",
    "        carlist = sorted(carlist,key = itemgetter(0), reverse = True)\n",
    "\n",
    "        for i in range(carlen):\n",
    "            if i in car_lined:\n",
    "                continue        \n",
    "                \n",
    "            car_lined.add(i)\n",
    "            carlines[i] = [i]\n",
    "\n",
    "            for j in range(i+1,carlen):\n",
    "                if j in car_lined:\n",
    "                    continue\n",
    "                \n",
    "                dis_gap = carlist[i][0] - carlist[j][0]\n",
    "                speed_gap = carlist[j][1] - carlist[i][1]\n",
    "                \n",
    "                \n",
    "                if (dis_gap > 0 and speed_gap <= 0) or (dis_gap == 0 and speed_gap < 0):\n",
    "                    continue\n",
    "                \n",
    "                if  dis_gap/speed_gap*carlist[i][1] > (target - carlist[i][0]):\n",
    "                    continue\n",
    "                \n",
    "                car_lined.add(j)\n",
    "                carlines[i].append(j)\n",
    "                \n",
    "        \n",
    "        return len(carlines)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catch(self, target, pos1, v1, pos2, v2):\n",
    "        if v1 >= v2:\n",
    "            return False\n",
    "\n",
    "        time = (pos1 - pos2) / (v2 - v1)\n",
    "        return pos1 + time * v1 <= target\n",
    "\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        pos_speed = list(zip(position, speed))\n",
    "        pos_speed.sort(key = lambda x : (-x[0], x[1]))\n",
    "        mono_stack = collections.deque([])\n",
    "\n",
    "        for pos, v in pos_speed:\n",
    "            if mono_stack and self.catch(target, mono_stack[-1][0], mono_stack[-1][1], pos, v):\n",
    "                continue\n",
    "            else:\n",
    "                mono_stack.append((pos, v))\n",
    "        return len(mono_stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        len1 = len(position)\n",
    "        \n",
    "        times = [[]] * len1\n",
    "        for i in range(len1):\n",
    "            time_tmp = (target - position[i]) / speed[i]\n",
    "            times[i] = [position[i], time_tmp]\n",
    "\n",
    "        print(times)\n",
    "\n",
    "        times = sorted(times, reverse = True)\n",
    "\n",
    "        print(times)\n",
    "        \n",
    "        out_val = 1\n",
    "        base_val = times[0][1]\n",
    "        for i in range(1, len1):\n",
    "              if times[i][1] > base_val:\n",
    "                  out_val += 1\n",
    "                  base_val = times[i][1]\n",
    "        return out_val\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        cars = sorted(zip(position, speed))\n",
    "        times = [float(target - p) / s for p, s in cars]\n",
    "        print(times)\n",
    "        ans = 0\n",
    "        while len(times) > 1:\n",
    "            lead = times.pop()\n",
    "            if lead < times[-1]: ans += 1  # if lead arrives sooner, it can't be caught\n",
    "            else: times[-1] = lead # else, fleet arrives at later time 'lead'\n",
    "        print(bool(times))\n",
    "        return ans + 1 # remaining car is fleet (if it exists)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        car_dict = {position[i]: (target - position[i]) / speed[i] for i in range(len(position))}\n",
    "        car_dict = {k: car_dict[k] for k in sorted(car_dict, reverse=True)}\n",
    "        count = 0\n",
    "        cur_time = -1\n",
    "        for _, t in car_dict.items():\n",
    "            if t > cur_time:\n",
    "                count += 1\n",
    "                cur_time = t\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]):\n",
    "        if len(position) == 1:\n",
    "            return 1\n",
    "\n",
    "        list1 = []\n",
    "        for i, value in enumerate(position):\n",
    "            time = (target - value) / speed[i]\n",
    "            list1.append([value, time])\n",
    "        \n",
    "        list1.sort(key=lambda x: -x[0])\n",
    "        \n",
    "        n = 1\n",
    "        cn = list1[0][1]\n",
    "        \n",
    "        for i in range(len(list1)):\n",
    "            if cn >= list1[i][1]:\n",
    "\n",
    "                continue\n",
    "            n += 1\n",
    "            cn = list1[i][1]    \n",
    "\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        x = list(zip(position, speed))\n",
    "        x.sort(key = lambda x: x[0])\n",
    "        print(x)\n",
    "        times = [(target - pos) / sp for pos, sp in x] \n",
    "        print(times)\n",
    "        res = 1\n",
    "        last_time = times[-1]\n",
    "        for i in range(len(times) - 2, -1, -1):\n",
    "            if times[i] > last_time:\n",
    "                last_time = times[i]\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]):\n",
    "        if len(position) == 1:\n",
    "            return 1\n",
    "\n",
    "        list1 = []\n",
    "        for i, value in enumerate(position):\n",
    "            time = (target - value) / speed[i]\n",
    "            list1.append([value, time])\n",
    "        \n",
    "        list1.sort(key=lambda x: -x[0])\n",
    "        \n",
    "        n = 1\n",
    "        cn = list1[0][1]\n",
    "        \n",
    "        for i in range(len(list1)):\n",
    "            if cn >= list1[i][1]:\n",
    "                cn = max(cn,list1[i][1])\n",
    "                continue\n",
    "            n += 1\n",
    "            cn = max(cn,list1[i][1])\n",
    "\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:\n",
    "        n = len(position)\n",
    "        # cars = [ps for ps in zip(position, speed)]\n",
    "        # cars.sort(key=lambda c: -c[0])\n",
    "        # times = [(target-p)/s for p, s in cars]\n",
    "        cars = sorted(zip(position,speed), key=lambda c: -c[0])\n",
    "        times = [float(target - p) / s for p , s in cars]\n",
    "        parents = [i for i in range(n)]\n",
    "\n",
    "        def root(i):\n",
    "            if parents[i] != i:\n",
    "                parents[i] = root(parents[i])\n",
    "            return parents[i]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            r = root(i-1)\n",
    "            if times[i] <= times[r]:\n",
    "                parents[i] = r\n",
    "        \n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            res.add(root(i))\n",
    "\n",
    "        return len(res)\n",
    "\n",
    "        # cars = sorted(zip(position,speed))\n",
    "        # times = [float(target - p) / s for p , s in cars]\n",
    "        # ans = 0\n",
    "        # while len(times) > 1:\n",
    "        #     lead = times.pop()\n",
    "        #     if lead < times[-1]:\n",
    "        #         ans += 1\n",
    "        #     else:\n",
    "        #         times[-1] = lead\n",
    "        # return ans + bool(times)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
